Given a predefined history tree, as illustrated on the left drawing of FIG. 1, of a declarative modeling system, and given the input buckets of the predefined history tree, declarative features, when instantiated, spread basic volumes among input buckets. Consequently, after some features are instantiated, each input bucket combines a plurality of basic volumes through a commutative operation (mainly a Boolean union noted “+”). Currently, each combination of basic volumes is implemented by an ordered list where volumes are stored according to creation sequence, as illustrated by the right drawing of FIG. 1. On figures, the root node is noted RN, leaf nodes are noted LN, and internal nodes are noted IN, and arcs or edges link nodes.
It should be noticed that the update of a declarative solid involves two steps. The first step is to update input buckets (lists of unions of basic volumes) and the second step is to update the predefined history tree, where commutative and non-commutative operations are stored. According to industrial testing, the very first implementation of declarative modeling technology shows that overall computing time is mainly spent in the predefined history tree update (as opposed to input buckets update time). But, recent performance enhancements in this field (through ongoing Dassault Systèmes (Assignee) patents: EP2474928, EP2474929 and EP2474930) reduced the update time of the predefined history tree in such a way that the basic volumes update time is now significant, and thus deserves optimization.
As it will be detailed in the following, the invention makes an intensive use of the “optimal binary tree” concept. This concept is well known in the art of sorting and searching ordered data (named “records”) in a dictionary. According to the art of sorting and searching, the so called “binary search tree” is updated each time a new record is added to the dictionary and its structure is designed to facilitate searching a given record. The searching efficiency is based on the binary tree balance. For this purpose, elaborated algorithms exist to maintain this balance each time a new record is added to the dictionary. Searching skill is used for database management as well as computational geometry. The classical reference is the book of D. Knuth: “Sorting and searching”.
As explained before, each input bucket of the predefined history tree combines its basic volumes through an ordered list. When the user modifies a declarative feature of the part, basic volumes modifications (deletion, dimension change, position change . . . ) are executed and input buckets need to be updated. This results in a large update time because updating each list is proportional to the age of the modified volume. It is well known from the solid modeling art that an ordered list is not the best structure from the update time point of view.
Another problem of the background art is the following. Declarative modeling technology is designed to behave independently of features creation order. Dassault Systèmes (Assignee) patent EP1501026 guarantees that the shape of the resulting solid is independent of the features creation order. But, the list implementation of input buckets makes the update of an early feature longer than the update of a late feature, which clearly contradicts the user perception of what should be a declarative behavior.
The art of searching is to maintain the balance of the binary search tree. The topology of the binary search tree captures a structure that is highly related to the fact that leaf nodes are ordered records. For example, the typical requirement is that all nodes of the left sub tree are lower (according to the records ordering) than all nodes of the right sub tree. This is the source of the complexity of balancing algorithms.